package pfq.demo.algorithm.sort;

import java.util.Arrays;

/**
 * 选择排序:
 * <p>
 * 每次从未排序的元素中选出最小（最大）的那个元素依次放到数组的左边（右边）
 * <p>
 * 时间复杂度为
 * 最好：O(n^2)
 * 最坏：O(n^2)
 * 平均：O(n^2)
 */
public class SelectSort {

    public static void main(String[] args) {

        int[] data = Arrays.copyOf(Utils.data(), Utils.data().length);
        System.out.println("排序前：" + Arrays.toString(data));
        selectSort(data);
        System.out.println("排序后：" + Arrays.toString(data));

    }

    /**
     * 简单的选择排序
     *
     * @param arr 待排序的数组
     */
    public static void selectSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            // 每次取出未排序中的第一元素
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {

                // 每次将较小值的索引赋给minIndex
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }

            }
            // 交换
            Utils.swap(arr, minIndex, i);

        }

    }


}
